# 力扣1584. 连接所有点的最小费用.py
# 给定一个无向图，图中每个节点的坐标为(x, y)，每个节点间的边的权值为两节点之间的欧几里得距离。计算连接所有点的最小费用。
import math

# 计算两点间的欧几里得距离
def distance(p1, p2):
    return math.sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2)

def solve(points):
    n = len(points)
    # Kruskal算法需要一个并查集结构来判断是否形成环
    parent = list(range(n))
    
    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]
    
    def union(x, y):
        rootX = find(x)
        rootY = find(y)
        if rootX != rootY:
            parent[rootX] = rootY
            return True
        return False
    
    # 构建所有可能的边（即所有两点之间的距离）
    edges = []
    for i in range(n):
        for j in range(i + 1, n):
            edges.append((distance(points[i], points[j]), i, j))
    
    # 按照边的权重（距离）进行升序排序
    edges.sort(key=lambda x:x[0])
    
    result = 0
    for weight, u, v in edges:
        if union(u, v):
            result += weight
    return result

if __name__ == "__main__":
    result = points = [[0,0], [2,2], [3,10], [5,2], [7,0]]
    print(solve(points))  # 结果：20.755685
